The rendering of transparent objects in computer graphics can be expensive. Generally speaking, transparency is a global illumination method, that is, it requires random access to geometric primitives of a scene stored in computer memory. Good approximations of transparency can be computed, however, with local illumination methods, that is, methods which require access to only a single geometric primitive. The primary advantage of computing transparency with a local illumination method is speed and efficiency, as the transparency can in this case be achieved without requiring all geometric primitives in the scene to be stored in computer memory for random access. This is important when rendering large scenes, e.g., scenes with so many geometric primitives they do not fit within the virtual memory of a computing environment.
Several approaches to computing transparency as a local illumination method exist in the prior art. All of these approaches fall generally into one of four different categories, e.g., order-dependent, order-independent, “depth-peeling,” or “screen door.”
The first category involves methods which are order-dependent, that is, all transparent geometric primitives in the scene are processed in a particular order. For example, if all such geometric primitives having the greatest distance from the viewpoint are processed first, then transparent objects closer to the viewpoint can be blended with pixels from previously rendered objects further from the viewpoint. This method is sometimes referred to as the “painter's algorithm.” Although conceptually simple, such order-dependent methods tend to work only in highly contrived situations; as is widely known, for example, such a method is not capable of calculating correct solutions for scenes comprised of interpenetrating objects. Furthermore, because all geometric primitives in the scene must be sorted before rendering of the scene begins, it can be prohibitively expensive and in some cases completely intractable. This is especially true for large scenes comprised of millions or billions of geometric primitives.
To remedy the shortcomings of such order-dependent methods, several categories of order-independent methods were developed. One popular method was developed and implemented in Pixar Corporation's RENDERMAN image processing software by Loren Carpenter, i.e., “The A-buffer, an Antialiased Hidden Surface Method,” Carpenter, Loren, Computer Graphics 18.3, 1984. In this method, lists of accumulated fragments of transparent geometric primitives are associated with each pixel in the image. To calculate the final transparency contribution of the fragments, each list in each pixel is sorted in back-to-front order so the fragments of each list can be blended together properly. This is essentially the same method as the “painter's algorithm,” except the sorting occurs after geometric primitives have been converted into fragment-lists. Unlike the “painter's algorithm,” the A-buffer is a high quality transparency method which properly handles interpenetrating objects and does not require geometric primitives in the scene to be processed in any particular order. For this reason, it is considered an order-independent method, even though sorting still occurs on the fragment-lists. By far the most problematic and inconvenient aspect of this method is that the fragment-lists consume large amounts of memory. Furthermore, knowing in advance how much memory is required to render a particular scene is a hard and usually intractable problem to solve. Depending on the scene, the memory requirements may be unbounded for all that computationally matters. As a result, this method can often exhaust available memory resources, resulting in system crashes by causing out-of-memory conditions. More recent refinements of this method, e.g., “R-Buffer: A Pointerless A-Buffer Hardware Architecture,” Wittenbrink, Craig, Proceedings of the ACM SIGGRAPH/Eurographics Workshop on Graphics Hardware, 2001, attempt to minimize the memory consumption problem by “recycling” available memory resources. Although this alleviates the problem for some typical scene conditions, it is by no means a robust approach which guarantees a bound on memory usage.
Another order-independent method popular in the prior art trades the problem of large and potentially unbounded memory consumption for the cost of multiple render passes. Originally introduced by Abraham Mammen, i.e., “Transparency and Antialiasing Algorithms Implemented with the Virtual Pixel Maps Technique,” Mammen, Abraham, IEEE Computer Graphics Applications 9.4, 1989, methods in this category are more commonly known today as “depth peeling.” In this method, a dedicated framebuffer with a fixed number of bits per pixel is employed to compute a transparency effect in multiple passes, that is, the entire scene, or portions thereof, are repeatedly rendered, or processed, multiple times. Many modern variations of the depth-peeling method exist, most notably U.S. Pat. Appl. Pub. No. 20040169650 entitled DIGITAL IMAGE COMPOSITING USING A PROGRAMMABLE GRAPHICS PROCESSOR, which describes a highly optimized depth-peeling technique for modern programmable graphics processors. Depth-peeling techniques are well-suited for hardware implementations because they require only a constant amount of memory which is deterministically a function of image resolution. A primary disadvantage is that multiple-passes require extra computation time as well as an ability to efficiently “redraw” the entire scene, or portions thereof. In most practical implementations, this means storing at least a portion of the scene in computer memory so that the “redraws” can be done quickly, thereby destroying the true nature of the otherwise constant memory requirements. In other words, typical implementations still require a variable amount of memory to “cache” portions of the scene so that multiple-passes can be quickly computed.
Last but not least, a final category of order-independent methods known collectively as “screen door” transparency offers a true constant-memory solution, but at the cost of an inability to achieve high-quality results. Consider, for example, that such methods are also commonly known by people skilled in the art as the “cheesy translucency” effect, e.g., “OpenGL Programming Guide,” Woo, Mason, et. al., Addison Wesley, 2005. The screen door transparency method involves creating a stipple pattern which is a function of the transparency of a geometric primitive. The stipple pattern is then used during the rendering process as a mask to prevent a portion of the rasterized fragments of the geometric primitive from contributing to the reconstruction of an image. The result is a transparency method which simulates the effect of looking through a screen door, where the density of the mesh of the screen on the door determines the amount of “transparency.” Such transparency methods are extremely well-suited for hardware implementations because they are order-independent, operate in a single pass and require only a strictly deterministic and constant amount memory.
The main drawback of “screen door” transparency is its inability to properly “accumulate” the contribution of overlapping transparent objects in the final image. This is a consequence of the previously described stipple pattern used by the method. Consider, for example, two overlapping transparent geometric primitives that both have the same amount of transparency. In this case, both objects must also have the same stipple pattern. As a consequence only the object which is processed first, or, if depth-buffering is performed, only the object closest to the viewpoint will be visible. This destroys the realism of the transparency effect, effectively limiting the method to scenes which have no overlapping transparent objects. Some efforts have been made to ameliorate this problem. The publication “Pixel Masks for Screen-Door Transparency,” Mulder, J., et. al., VIS 98: Proceedings of the Conference on Visualization, IEEE Computer Society, 1998, is one example, and it is incorporated herein by reference. But such efforts only offer marginal improvements for a small case of limited and/or contrived circumstances. No general solutions in the prior art exist. The most likely reason for this is that practitioners and people skilled in the art largely view the method as a cheap but low-quality hack, e.g., the “cheesy translucency” reference previously cited. As a consequence, there seems to have been little hope or no interest over the years to ever consider its potential as a method to provide high-quality results.
In summary, FIG. 1 is a tabulated feature comparison of prior art transparency methods. As can clearly be seen, all prior art methods have an Achilles heel. The “painter's algorithm” is not order-independent, and it cannot properly handle scenes with interpenetrating objects. The A-buffer method allows objects in the scene to be processed in any order, but the memory requirements are large and hard to anticipate, making the method prohibitively expensive in some cases. Depth peeling methods can operate within a constant memory footprint, or within a generally bounded amount of memory, at the expense of requiring multiple passes, i.e., the entire scene, or portions thereof, must be processed and/or rendered multiple times. The screen door method is particularly efficient, but the quality is poor because the transparency of overlapping objects cannot properly “accumulate,” effectively limiting this approach to scenes comprised of non-overlapping transparent objects or situations where high-quality results are not important.
Clearly what is desired is a new and improved method of transparency in computer graphics which is order-independent, operates in a single pass, uses a deterministic and constant amount of memory, and is able to reliably generate high-quality and realistic images for scenes comprised of interpenetrating and/or overlapping transparent geometric primitives.